/*
题目链接：https://leetcode.cn/problems/longest-common-subsequence/description/
	刘沛民	2024-12-3
*/

class Solution {
public:
    int longestCommonSubsequence(string str1, string str2) {
	int n = str1.size();
	int m = str2.size();
	str1 = '#' + str1;
	str2 = '#' + str2;

	int dp[1002][1002];
	int s[1002][1002];

	// 根据状态转移方程列表
	for (int i = 0; i <= n; i++)
	{
		for (int j = 0; j <= m; j++)
		{
			if (i == 0 || j == 0) dp[i][j] = 0;
			else if (str1[i] == str2[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
			else if (str1[i] != str2[j]) dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
		}
	}
    return dp[n][m];
    }
};